//「一本通 3.2 例 2」拯救大兵瑞恩
//分层图加最短路径
#include <iostream>
#include <queue>
using namespace std;
const int MAXN=10;
const int MAXP=10;
const int INF=0x7fffffff;
int n,m,p;
int adj[1<<MAXP][MAXN+1][MAXN+1][MAXN+1][MAXN+1];//为0代表连通，为1代表不通
int key[MAXN+1][MAXN+1];
int dir_off[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct  Node
{
    int level;
    int x,y;
    int time;
};
queue<node> qu;
bool inqueue[1<<MAXP][MAXN+1][MAXN+1];
int mintime[MAXN+1][MAXN+1];
void spfa(){
    for(int x=1;x<=n;x++)
        for(int y=1;y<=m;y++) mintime[x][y]=INF;
    mintime[1][1]=0;
    int level=0;
    if (key[1][1]>0) level+=1<<(key[1][1]-1);
    qu.push({level,1,1,0});
    inqueue[level][1][1]=true;
    while(!qu.empty()){
        Node cur=qu.front();
        qu.pop();
        for(int d=0;d<4;d++){
            int newx=cur.x+dir_off[d][0];
            int newy=cur.y+dir_off[d][1];
            if (newx<1||newx>n||newy<1||newy>m) continue;
            
        }
    }
}

int main(){
    cin>>n>>m>>p;
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        int x1,y1,x2,y2,g;
        cin>>x1>>y1>>x2>>y2;
        if (g==0)
            for(int level=0;level<1<<p;level++) adj[level][x1][y1][x2][y2]=1;//这里的层次（level)其实就是含有
            //钥匙种类的二进制状态压缩
        else if (g>0){
            for(int level=0;level<1<<p;level++)
                if (level&(1<<(g-1))==0) adj[level][x1][y1][x2][y2]=1;
        }
    }
    int s;
    for(int i=0;i<s;i++){
        int x1,y1,q;
        cin>>x1>>y1>>q;
        key[x1][y1]=q;
    }

}